\setcounter{page}{1}


\section*{Responses to Reviewers' Comments}
We thank the reviewers and the associate editor for their helpful and detailed feedback. We address the comments below. Our response appears in bold.


\subsection*{Associate Editor's Comments}

The reviewers unanimously agreed that the paper is much improved from its original version; congratulations. I thus recommend that it be accepted subject to minor revisions.

The reviewers articulated two remaining concerns that strike me as important. First, Reviewer 2 identified problems in the way the work is delineated from past work. I agree with this assessment, and think this could be addressed pretty easily by toning down some of the claims of generality and dealing a bit more generously with previous work. 

\response{Throughout the paper, we have toned down the claims and addressed reviewer's comments regarding exposition of related work. In particular, significant additions and modifications have been made to the related work section starting on page~\pageref{rel_major_changes_begin}.}


Second, Reviewer 2 and (particularly) Reviewer 3 raise concerns about the generality of the methods, their succinct representation in a computer, and the ease with which an end user could apply them in a novel setting. Again, I don't think these concerns are too hard to address: I think the fix here is to explain very clearly what the proposed methods can and can't do, and what representational assumptions are required (or are sufficient) to make them feasible. (That is, I don't see a problem with the method's limitations; I just think these points need to be expressed clearly.)

\response{In terms of the limitations, the problem is not with storage or representation of the utility lines (as mentioned below, the algorithms are based on the expected utility functions, and only need to store one expected utility function per action which, in the case of linear utilities, means having 2 values per action: a slope and an intercept), but potentially with computation of individual utility lines, which is domain specific. We have clarified this throughout section~\ref{sec:linu}, by making the representation in the case of linear utility functions explicit both in the text and in the algorithms. Furthermore, in the last paragraph of section~\ref{sec:br}, we have emphasized that the computation of utility lines is domain specific and no general guidelines can be given to compute these.}

%The computation of a single slope and intercept could, in general, be exponential in the number of players and actions. Note that our general results (i.e., fictitious play, best response, and ``belief to strategy" algorithms) take utility lines as input, while computation of the lines is domain specific (input to the ``utility lines" algorithm is an entire game). We now discuss this explicitly in the last paragraph of Section~\ref{sec:bestresponse}, and hope that this is furthermore clarified by making the representation explicit in case of linear utilities.}

Beyond these points, the reviewers also caught a large number of smaller issues with the paper; I trust that the authors will want to fix these as well.

\response{We have addressed all comments by the reviewer, except in a couple of cases where we disagree, and we have clarified this in the response below.}

My hope is to review the changes myself, and to avoid sending the paper out to the reviewers a second time. To help me do this, I'd appreciate a point-by-point response to the reviewers' comments. If everything strikes me as resolved, I'll recommend acceptance of the paper myself at that point.

Again, congratulations!


\subsection*{Reviewer 1}
This paper provides an algorithm for solving a specific class of games called G-FACTs. These games have private values/incomplete information, finite action spaces, and continuous type spaces. The algorithm is based on an extension of fictitious play, and is shown to converge to an approximate pure-strategy Bayesian-Nash equilibrium. They prove the convergence formally, and demonstrate its efficiency in a variety of auction settings. 

The algorithm seems novel, and the results seem impressive. Equilibria are computed in several natural classes of games for which no prior algorithms have been developed. The evaluation is thorough.

Footnote 3 page 3: "`There is little behavioural support showing that people randomize when making decisions."'
Should give a reference here, e.g., Camerer "`Behavioral Game Theory"'

\response{Footnote~\ref{fn:pure} (page~\pageref{fn:pure}) has been rephrased and the reference has been added. It now reads: `Pure equilibrium is a preferred solution concept as it is conceptually simpler and it does not rely on the ability of a player to randomize (see, e.g., discussion on mixed equilibria implementation in~\cite{camerer_BGT_2003})'}

Page 5: it's specifically no-internal regret algorithms that converge to the set of correlated equilibria.
"`A number of other general purpose solvers exist for computing Nash equilibria [41, 40, 57, 21, 45, 26, 19, 29] ... However, our focus is on games of incomplete information"'
Some of these references are for computing correlated equilibria, not Nash equilibria: e.g., 45.
Also, several of them do apply to incomplete information games: e.g., 26, 19, 29.

\response{We have rephrased the text on page~\pageref{hoda_gilpin_koller_incomplete_but_discrete} to resolve this ambiguity. Indeed some of the algorithms (26,19,29 -- Hoda et al, Gilpin et al, Koller et al -- among them) can be applied to games of incomplete information. However, they rely on the type-space being discrete and finite, making them inapplicable to our setting, where the type space is continuous.}


Bottom pf pg 5: Koller et al algorithm does not convert extensive-form games into normal-form (which has an exponential blowup). It converts the game to sequence form, which is linear in the size of the game tree.

\response{Indeed a slight misuse of terminology on our part. A sequence matrix form, not purely normal form, was meant. We have corrected the text to clarify the issue and explicitly point out the conversion steps and their effects. In particular, it still holds that the conversion in general entails exponential increase in the size of the problem, albeit there are some sub-classes of games where this does not occur.}


Pg 5-6: in addition to CFR and fictitious play, should discuss the LP formulation of Koller et al, which implies to two-player zero-sum imperfect information games with perfect recall, as well as the excessive gap technique which applies to similar games (e.g., Gilpin et al and Hoda et al).

\response{We have modified the text (Page~\pageref{hoda_gilpin_koller_incomplete_but_discrete}, para starting with ``The literature mentioned above...'') to better and more explicitly reflect the strength of Koller's technique, as well as those of Gilpin et al and Hoda et al. Specifically, that they can be applied to incomplete information games with discrete and finite type spaces. However, since our paper deals with continuous type games, these techniques are still inapplicable to our domain of interest.}


Pg 6: "`On the other hand in this paper we tackle such games by creating a version of fictitious play generalised to incomplete information settings."' You just described other algorithms that apply fictitious play/regret minimization to incomplete information settings; the "`on the other hand"' statement implies that you didn't. 


\response{Fixed. New version reads "`In contrast, our techniques is designed for games with continuous types."'}


Pg 6 footnote 4: That algorithm does not discretize the type space, though it does assume a pre-determined finite structure. The approach of this submitted paper does this as well, at least in the linear utility case, since the number of utility lines equals the number of actions, and the best response will correspond to basically breaking up the type space into a finite number of intervals.

\response{It is true that our algorithm ends up breaking up the type space into a finite number of intervals, but the point is that, in our case, the number of intervals and actions associated with each interval are not pre-determined (i.e. unlike the Ganzfried\&Sandholm paper we assume no knowledge about the number of intervals and actions associated to each interval). However, we agree that the comment regarding discretisation is not justified by this being pre-determined. To clarify the approach used by Ganzfried  and Sandholm in their AAMAS 2010 paper, and how this differs from our approach, we have rewritten the paragraph on the poker competition games (starting from page \pageref{related_poker} final paragraph), and discussed the paper in more detail in the text (as opposed to using footnotes). Here, we mention that the algorithm proposed by Ganzfried  and Sandholm  consists of solving a mixed integer linear feasibility program and importantly relies on the type space to be discretised. They do also discuss an extension on how to cope with continuous type spaces, but this extension assumes piece-wise linear type distributions. The main algorithm is still essentially based on a discretisation of the type space. We explain this and other differences in the text.}


Definition 3: should probably define "`almost"' formally if you want to use it in a definition.

\response{Given together with a reference distribution ($F$ in this case) and a condition, ``almost'' means that the set of all instances where the condition fails has probability zero. This is the standard meaning of the word ``almost'' in probabilistic statements. Nevertheless, footnote~\ref{fn:almost} has been placed on page~\pageref{def:eqactions} within the definition to clarify the word.}



Page 9: "`We note that limiting our analysis to symmetric pure strategy equilibrium is justified since such an equilibrium is known to exist in this class of games ..."' Should make this rigorous as a Proposition/Theorem, since it is so central to the theory of the paper. Footnote 5 is also too loaded. I'd recommend doing a formal theorem with a full proof, rather than summarizing the proof in a footnote.

\response{We have revised the text to make the statement more prominent (see Proposition~\ref{prop:pure_ne} on page~\pageref{prop:pure_ne}). However, its proof follows directly and immediately from other results and, therefore, cannot be stated here as a theorem contribution. We point out the literature source explicitly in the Proposition's title.}


Page 10: "`Furthermore, general computational techniques for deriving equilibria in games of incomplete information are restricted to settings with finite type sets."' The authors already mentioned at least one paper that does apply to continuous type sets "`Ganzfried/Sandholm, AAMAS 2010."' Another relevant paper is "`Automated Action Abstraction of Imperfect Information Extensive-Form Games"' by Hawkin/Holte/Szafron, AAAI 2011. This algorithm applies to imperfect-information games with finite type sets, but continuous action spaces (e.g., bet sizes in no-limit poker).

\response{We have rephrased the sentence to say "`Furthermore, general computational techniques for deriving equilibria in games of incomplete information are *typically* restricted.."'. Furthermore, as mentioned earlier, we have now extensively discussed the Ganzfried/Sandolm AAMAS 2010 paper in the related work section. Finally, we have added the Hawkin/Holte/Szafron, AAAI 2011 paper  (see page \pageref{related_poker} final paragraph, reference \cite{hawkin2011automated}).} 
 

Page 10: $s'_t$ seems to refer both to the vector of opponents' mixed strategies and to our strategy. Should probably add extra subscript of i/-i to make the players clear.


\response{In the pseudocode for FP, we implied only 2 players. We incorrectly referred to multiple opponents, which would have required the use of $s_{-i}$. We now speak of a single opponent, whose strategy is $s'_t$. We avoid the $-i$ notation throughout the paper as we only deal with symmetric strategies.}


Figure 1: Perhaps the alpha(t) function be treated as an input to the algorithm.


\response{Fixed.}


Pg 12: $d(h^T - h*) -> d(h^T, h*)$
 LINE 35 - TYPO

\response{Fixed.}




Pg 13: Shouldn't use alpha again in a different context, since it is already defined as the decay function in fictitious play. 

\response{We no longer overload $\alpha$.}



Should probably give a formal definition of "`upper envelope,"' since it is central in the analysis.

\response{Included a mathematical definition of upper envelope to clarify this.}


Figure 4 pg 15: The title of the algorithm should make it clear that this is just the specific instantiation of the BestResponse function for the linear utility/single parameter setting. Same with BeliefsToStrategy on the next page.


\response{The titles of both figures now make this clear. We are not sure whether the reviewer was suggesting changing the names of the algorithms but we found that it would make things more confusing as we want to instantiate the algorithms \br\ and \btos, which are mentioned in a more general context in Figure~\ref{fig:fp}. We feel there is no risk of confusion as we state repeatedly the algorithms are for the special case of linear utilities, and they appear in the corresponding section.}


"`The BeliefsToStrategy algorithm in Figure 5 has three important properties ..."'
I'd state the properties formally, maybe as propositions.


\response{
We rewrote the paragraph. Properties 2 and 3 are formally stated as theorems~\ref{b2s_in_eq} and~\ref{b2s_is_epsilonning} respectively.
}


The authors discuss a procedure of removing actions that appear with probability below some threshold delta (e.g., bottom of page 18). They also discuss a "`purification"' procedure for constructing pure strategies. Another revelant paper is "`Strategy Purification and Thresholding: Effective Non-Equilibrium Approaches for Playing Large Games"' by Ganzfried/Sandholm in AAMAS 2012, which shows that similar purification/thresholding procedures can be used to overcome the effects of overfitting due to abstraction.

\response{We have added the reference~\cite{ganzfried_sandholm_waugh_2012} on page~\pageref{fn:g-s-w}. However, it is important to notice that the ``purification'' and ``thresholding'' terms used in the G/S/W paper differ from those used in our paper. In particular, both the purification and thresholding in G/S/W operate and maintain (explicitly) mixed strategies, while our paper explicitly maintains a pure strategy. Nonetheless, the methods are similar in their intent and support each other's findings and validity.}




Page 34, Section 7: Should state that one of the main purposes of this section is to derive analytical results in order to verify the quality of the solutions computer by the algorithm that was previously described. This would tie it in better to the preceding sections.


\response{We added the sentence at the end of Section 6 to make the transition to Section 7 smoother: ``In the next section we provide analytical characterization of equilibria. The equilibria that we derive there analytically confirm our numerical results from in Section~\ref{sec:hom}."

We present results in Section 7 as a theoretical contribution that is of value beyond confirmation numerical results.
}


Page 42: What year is reference [53] from (it's omitted in the references)? 

\response{The paper was published in 2010.  Oddly enough, the Elsevier LaTeX style file we were using omitted year and other information from proceeding publications. We have now used a different style file and checked that all references are complete.}



\subsection*{Reviewer 2}
The revised version addresses to a significant extent my primary concerns about the original submission.  The assumptions are now more clearly stated, and there is substantial new material evaluating the computational performance of the algorithm.  I think there remains room for improvement in both areas, as well as general clarity of presentation.  

Restrictiveness of assumptions.  As noted, the statement of assumptions is now much clearer.  I agree that in this paper linearity is not assumed in the general FP algorithm, but is required by the particular instance exhibited for BeliefsToStrategy.  Of course we do need a B2S to use FP, so it remains open whether it can be accomplished practically for nonlinear utility.  That said, I also now agree that linearity may not be too onerous once we have already assumed single-dimensional types, as long as there is a natural ordering of types these can be rescaled.  However, I would still argue that single-dimensional types is a severe restriction, particularly for the highlighted application of simultaneous auctions.  I don't think we need to resolve this argument, though, for purposes of deciding whether to accept the paper. 


\response{We agree with the reviewer that single-dimensional type is a restriction. The following explanation appears when we introduce the simultaneous auctions model: ``We acknowledge that single-dimensional types are much more restrictive than multi-dimensional types that allow each bidder to have his own complementarity structure. However, our restricted model is a good approximation for scenarios where items are likely to have a common complementarity structure (e.g., the bundle of left and right shoe is valuable, while each item in isolation is worthless)."}


I do find that the repeated assertions about the generality of the methods are tedious and unconvincing.  This, combined with a generally defensive and disparaging tone when discussing related work really detracts from the paper.  Of course it is useful to explain how the current work overcomes limitations in prior literature, but it is unnecessary and inaccurate to suggest the impression that all prior work is severely limited while the current work is completely general.    


\response{We have removed repeated claims about generality, as well as claims that related work is severely limited. We also more clearly highlight the limitations of our own work.}


Computational characterization.  I appreciate the new material about computational performance.  However, I still do not see any general characterization of runtime as a function of number of players, number of auctions, and bid levels.  The results for bid levels $> 10$ seem to all have two players and two auctions.  There is likewise no clear statement of what exactly is the envelope of problems you have been able to solve.

\response{We neglected to mention all the settings, and have now corrected this. We do in fact show results for $> 10$ bid levels and $> 2$ players. In particular, Figure \ref{fig:time_d} on page \pageref{fig:time_d} shows how the computational time increases with bid levels for up to 100 bid levels per auction, and for n=10 bidders. We note, however, that we use the approximate tie breaking rule in this case, and so the number of bidders does not affect the computational time of a single iteration (unlike in Figure \ref{fig:time_n} on page \pageref{fig:time_n} where we use the exact tie breaking rule -- we now make this explicit in the figure captions). In all experiments we only consider 2 auctions, since the number of actions increases exponentially with the number of auctions, and becomes very large very quickly. So it is clear that the approach does not scale well with the number of auctions (unless the number of bids per auction is very low). In terms of the envelope of problems that we have been able to solve, it is difficult to give a definite answer, since it depends on the desired precision, the number of runs, and on how much time one is willing to wait for the results (i.e. an hour vs a few days). Our aim was to give a general idea of the scalability by showing the time required as a function of the number of players and bid levels per auction.}



General exposition.  It seems that most of the detailed issues pointed out have been resolved (though several of the problems below persist despite being pointed out in the original review), but I think the paper could benefit from a general pass to improve the clarity.  Here is another (but non-exhaustive) set of detailed comments, combining substantive and exposition-related matters. 

p.1. abstract.  The second sentence will be confusing to someone who has not read the paper and is only reading the abstract.                

\response{We rephrased the sentence.}




p.1, l27.  auctions are mechanisms, not games.  An auction combined with a specification of players and type distributions defines a game.

\response{Rephrased the sentence.}


p.1, l32.  Substitutes and complements are properties of preferences, not of items.

\response{The terms ``substitutes" and ``complements" are commonly used to refer to items (e.g., see ``Introductory Economics" by Hoag, A.J. and Hoag, J.H. 2002 page 65.). We feel there is no imprecision/confusion there.}


p.2, l8.  "`To this end"'  Not at all clear what "`end"' is meant here.  This phrase appears many times, often inaptly.


\response{Rephrased the sentence.}


p.2, l29 "`most other solvers"' -- not clear what this refers to

\response{
The text has been rephrased, and the sentence is no longer there.%
%The phrase refers to other NE computational techniques more explicitly listed in our related work section. The sentence has been rephrased to resolve the ambiguity.
}


p.2, l31 replacing "`standard"' with "`common"' does not fix the problem



\response{
We now say ``Following much of the game-theoretic literature (see, e.g.,~\cite{krishnabook,mwg})".
}

p.2, l44 the fact that an action space "`can easily be"' discretized does not really entail anything.  It all comes down to what might be lost in terms of accuracy, as a function of computational cost.

\response{
We removed the claim in question and instead say: ``In fact, in many cases, such as auctions with discrete bids (consider the auctioneer {\em stepping} up the price in an English auction), finite action spaces are inherent to the problem, yet more difficult to analyse theoretically."
}


p.3, footnote 3 is not convincing

\response{
Rephrased the footnote.
}



p.4, l12.  mention assumption that types are one-dimensional  


\response{Done.}

p.5, l21.  Avoid scare quotes (i.e., in 'tree games'). Either describe or use some standard term.

\response{We have removed the quotation marks and added an explicit sentence to clarify the model. Specifically, that ``utility structure induces a set of dependencies between players that form a tree''.}


p.5, l33   grammatically awkward -- what is inapplicable?  Also, the discussion of using BAGGs for continuous types seems gratuitous -- has anybody proposed this?


\response{We fixed the sentence and removed the discussion about BAGS/MAIDs with continuous types.}

p.5, l40  MAIDs   


\response{Removed the sentence with this word.}


p.6, l4  convoluted sentence


\response{Rephrased.}


p6, l15. Last sentence of paragraph is superfluous.


\response{Removed.}


p6, footnote 4.  No, the qualitative models of G\&S define a structure on the strategy mapping types to actions.  This is not at all tantamount to discretizing the type space.

\response{We agree with this comment. We have replaced the footnote by a more detailed discussion of the G\&S paper in the main text of the related work section. We discuss how their approach differs from ours, and where the discretisation of the type space comes to play in the G\&S paper: this is in fact not because of the mapping, but because finite types is an integral part of their mixed integer linear feasibility program (MILFP). This is now explained in Section \ref{sec:related} on page \pageref{related_gs}.} 


p7, first para. of Section 3.  It is unclear whether and where you are invoking a symmetry assumption.  The notation does not require symmetry, and in fact nowhere is symmetry defined.  This needs to be remedied.  A technical symmetry condition would have to be cast as a constraint on the utility function.


\response{
We added footnote~\ref{ft:sym} to remedy this.
}



p9, The mere fact that a symmetric equilibrium exists cannot be said to *justify* limiting attention to such solutions.

\response{``Justify'' here was used in the sense of ``allow and enable'', and we have reformulated the text accordingly to remove the ambiguity. In particular, existence of a pure strategy equilibrium in G-FACTs {\em allows and enables} us to use pure strategies without loss of solvability. I.e. all G-FACTs can be solved in pure strategies. Proposition~\ref{prop:pure_ne} on page~\pageref{prop:pure_ne} was created to make the statement more formal.}



p12, Corollary 1.  s* is still not defined.  You have introduced the symbol s* in the Thm 1 statement: "`there exists a strategy s* that..."'.  This does not make it available outside the scope of its quantifier.


\response{Fixed.}



pp14-16, algorithms.  These algorithms could be substantially clarified.  The indexing and sorting of actions is still quite muddled.  You mention in a comment that of BestResponse that the actions are sorted by slope somehow (and here and elsewhere -- it is their utility lines that have slope not the actions).  It would be more sensible to make this sorting an explicit part of the algorithm UtilityLines.  The meaning of action indices is very confused.  You say $a_i$ in A, suggesting that there is an inherent index for each action.  Then at other times you assume a sorting, where presumably the index meaning is changed.  In algorithm BestResponse you use i as a generic subscript (step 1), then overload it with a particular meaning (steps 2 and beyond).  Finally, you need to give an intuitive explanation for the mathematical expressions in BeliefsToStrategy.  Currently these are interpreted only in the proof.


\response{We have clarified the pseudocode and added explanations, in particular for the BestResponse algorithm. We have also introduced separate notation $L$ for utility lines. We attempted including explicit ordering of actions in pseudocode but found that it made notation too confusing. Instead, we still refer to $a_i$ as the action with $i$th lowest slope but explicitly state that we abuse notation by doing this.}


p17, l24. complement


\response{Fixed.}

p19, l37. seems to suggest (incorrectly) that "`items are perfect substitutes"' is equivalent to "`bidder only requires a single item"'


\response{Changed to ``the bidder does not derive extra benefit from winning more than one item"}


p19, l42. "it should be noted that" is rarely a useful phrase


\response{Rephrased.}

p19, footnote 54.  Seems rather strange: why not just use the correct technical terms for what you mean?


\response{Fixed.}

p20, l14. What exactly is claimed to be "`natural in practice"', and what does that mean?  The real question is whether treating bids as a finite set of actions is viable for game-solving, which has more to do with the computational practicality of handling the entire relevant action space.  This is not a question of what is "`natural"'.

\response{We have rephrased this as follows: 'We argue that having a finite set of bids is  not necessarily restrictive in practice, since bids are often rounded to an appropriate level (e.g. to the nearest dollar amount for small bids, the nearest ten-fold for larger bids, etc).' Furthermore, we have placed this in a footnote (see footnote \ref{fn2} on page \pageref{fn2}).}


p20, l52.  The upper bound for gamma here should be min(alpha,beta).


\response{Fixed.}


p20, l57.  mu and nu not defined


\response{Fixed.}


p21, l4.  "asymmetric" is not the right term here.  You mean that the goods are heterogeneous.


\response{We now say ``In addition, we can model auctions selling heterogeneous items."}

p21, l17.  To see the assertions of generality persist out to here is really grating.


\response{Removed the assertion.}


p21, l36.  Doesn't tie breaking come up in the cost determination as well?

\response{Yes, but tie breaking is much simpler to compute for the cost component, since this can be done for each auction independently (since the cost is the sum of expected costs for each auction, see Equation B.4 in Appendix B). This was briefly explained at the beginning of Appendix B.1, but we have now also added a sentence in the second bullet point on page \pageref{lab1} referring to Appendix B and saying that:
 'as can be seen in the appendix, note that the  expected payment is simply the sum of the expected payment for each auction, and is much easier to calculate since this can be done independently for each auction'}


p22, Table 1.  The symbol m is overloaded -- already used for number of actions, which now is changed to $|B|^m$. 

\response{Fixed. Now $p$ is used to denote the number of auctions.}


p25, Figures.  Need to give all the parameter settings.  How many bid levels in Fig 7?  How many bidders in Fig 8?  In caption of Fig 8, what is d?

\response{We have now added the parameter settings in the captions. The parameter d was incorrect, and should have been |B| (i.e. the number of discrete bids per auction). We have corrected this.}


p26, l30.  It is not clear what epsilon you are referring to here.  Is it a convergence parameter of FP, or the approximation value of the equilibrium?  In either case, the assertion that B2S is not necessary to compute epsilon bears some explanation. 

\response{Thanks for noticing this. We agree that this was not clear, and was actually strictly speaking incorrect since in the implementation we do use the B2S to compute convergence. Furthermore, instead of epsilon we mean the relative error as defined by Equation \ref{eq:relerror} on page \pageref{eq:relerror} (which is a scaled epsilon). We have now made a number of corrections and clarifications. First, we have changed Equation \ref{eq:relerror} to explicitly include the B2S algorithm, and explained this in the text above. Now it should be clear how we define the error. Where we incorrectly referred to epsilon, we have changed this to say 'error' instead. Finally, the sentence about the computation referred to by the reviewer has been moved to Footnote \ref{fn1} on p. \pageref{fn1} and now reads: 'Note that the computation of the \btos\ algorithm is negligible compared to the other algorithms since the main part consists of sorting the actions by slope. Furthermore, the \btos\ algorithm is only required to compute the relative error (Equation \ref{eq:relerror}), and the strategy itself once the process has converged.'}


p27, l7.  Is this for n=2?  Perhaps express in terms of n.

\response{Done.}



p29, l49.  "agents try avoiding winning a single item".  No, they *stop* trying to avoid winning both.

\response{We disagree here. The agents stop trying to avoid winning both after gamma=1.2 (since the f(1,1) line starts becoming strictly positive at this point). However, after gamma=2 (where the comment refers to), they entirely avoid winning a single item (i.e. f(0,1) and f(1,0) are zero).}



p34, Fig 14.  It should be possible to give more intuition for this result.  Near equilibrium, it should be that switching to the other good gains near-equal utility.    


\response{Not sure what the reviewer means here. Fig 14 shows *equilibrium* bids (the value of epsilon is very small). By the definition of equilibrium, whenever switching occurs (i.e., bid high on one good and low on the other and then reverse), it is the best response. However we are not sure how this provides more intuition.}


p36, Lemma 1. This proof might be relegated to an appendix.


\response{Moved.}

p38, l25.  This sentence is not a very intuitive explanation of the theorem -- it just refers to equations.


\response{Fixed.}

p41, l40.  Should that be $epsilon > 0$?


\response{Yes, fixed now.}


p41, l43.  Not clear what you mean by "General solvers"

\response{The phrase refers to NE solution algorithms applicable to large classes of games, and more explicitly those pointed out in our Related Work section (page~\pageref{sec:related} onwards). Paper text has been modified to resolve this ambiguity. We now explicitly point out ``(e.g., those listed in Section~\ref{sec:related})''.}



References.  Many of these are incomplete, missing years and page numbers.

\response{Oddly enough, the Elsevier LaTeX style file we were using omitted year and page numbers from proceeding publications. We have now used a different style file and checked that all references are complete.}


\subsection*{Reviewer 3}
The revisions have improved the paper substantially.  The assumptions (and their necessity) are more thoroughly explained and the relationships to previous work are much clearer.  The increased clarity of the revised version also makes it easier to identify the root cause of a few criticisms I had of the first draft: I believe that a reader intending to implement the FictitiousPlay algorithm for use on some novel G-FACT would encounter two major gaps.  These gaps should be clearly identified, even if they cannot be completely resolved. 

The first gap concerns the problem of how to efficiently represent a G-FACT in a computationally usable data structure.  At first, I could not figure out what the "natural, succinct" representation of a G-FACT would be.  (I am borrowing those terms from Papadimitriou and Roughgarden, 2008, which is also about efficiently computing equilibria to games with restrictive assumptions like symmetry and "anonymity.")  The G-FACT definition describes u as a mapping from Theta x $A^n$, so a natural representation might involve storing a slope and intercept for each element of $A^n$.  However, such a representation would be exponentially large and is not succinct because it does not capture the symmetry inherent in the game.  A succinct representation could still grow exponentially in n, when m=n for example.  In the end, I came to the conclusion that for large games the utility function would have to be implemented as a function and not as a table of slopes and intercepts.  Nevertheless,
I assumed that the per-iteration runtime would be small provided that function could be evaluated efficiently.

\response{Indeed an explicit representation of the terminal utility mapping is exponential in the number of players and not wieldy. However, our algorithms rely entirely on the expected utility $\uet(\type,\a,\d)$, and so there is no need to store (or even compute) the terminal utilities $u$. Therefore the table needs to contain only $|A|=m$ expected utility functions (in the linear case, this means $m$ slopes and intercepts), and not $|A|^n$ (even in the asymmetric case, this becomes $|A|*n$). We have now clarified this in particular in section~\ref{sec:br}, in a number of places. First, we more clearly define a utility line as expected utility (see Equation~\ref{def:utilityline}) and make the link explicit between linear utilities and linear expected utilities (see Footnote~\ref{fn:linear} on p. \pageref{fn:linear}). Second, throughout section~\ref{sec:linu}, including the UtilityLines and BestResponse algorithms, we have made the representation explicit by using to slopes and intercepts to represent a utility line. Finally, in the last paragraph of section~\ref{sec:br}, we explicitly mention that only $m$ utility lines need to be computed.}

%  These can often be succinctly represented and efficiently computed, since they are continuous (or a finite set of continuous) functions. In particular, for simultaneous auctions $\ue(\type, \a,\d)$ takes the form of a statistic (closed formula, polytime computable in all parameters except the number of auctions, see Equation~\ref{eq:ulsimauc} on page~\pageref{eq:ulsimauc} and Appendix~\ref{app:222}) and $\s(\type)$ is piece-wise linear due to its construction (see $\btos$ algorithm in Figure~\ref{fig:beliefsToStrategy} on page~\pageref{fig:beliefsToStrategy}). 

%In short, if a succinct game representation is needed, it is best to look at the expected utility as the source of succinct (and poly-time usable) representation. Notably, $\ue(\type,\a ,\d)$ does not depend on the number of players as an input parameter, and the number of players is not an issue for scalability.}
%


The second gap is much easier to identify, due to the revisions: In order to efficiently run FictitiousPlay on a linear-utility G-FACT, the reader would first need to invent an algorithm for computing the utility lines for that particular game. This was the issue that prompted my concerns about exponential costs in the first review: I strongly suspect that having a poly(n) algorithm for computing u(theta,$a_N$) is not sufficient to guarantee the existence of a poly(n) algorithm for finding utility lines.  (It's also confusing that the UtilityLines subroutine appears to return functions that can depend on $a_i$ and h.  It might be clearer to have a function that computes a single utility line given $a_i$ and h, and just returns the slope and intercept.)

\response{The reviewer is correct: computing the slope and intercept of a single utility line may not be poly(n). In the final paragraph of section~\ref{sec:br} we have now emphasized the fact that computing the utility lines depends on the specifics of the domain, and can be a bottleneck in practice, but we cannot analyse its complexity generally. 

In terms of the representation of a utility line,  in the beginning of section~\ref{sec:br}, we have now clarified that the slopes and intercept are constant for a given $a_i$ and $h$. Furthermore, we have followed the suggestion of the reviewer and the UtilityLines algorithm now explicitly returns a set of slopes and intercepts. Moreover, we now explicitly use the slope and intercept as a representation of utility lines in the BestResponse algorithm (see Figure~\ref{fig:brlinear}), as well as in the corresponding narrative on page~\pageref{ulalg}, and in the BeliefsToStrategy algorithm (Figure~\ref{fig:beliefsToStrategy})}

%% \response{The number of terminal utilities  is a^n --- too high --- so it's not interesting to talk about them.
%% terminal utility is expectation over which auctions you win - combinatorial already. - not exponential in the number of player. -- The suspicion is correct.}




